#include<bits/stdc++.h>
#define ll long long
#define L x<<1
#define R x<<1|1
#define mid ((l+r)>>1)
#define lc L,l,mid
#define rc R,mid+1,r
#define Root 1,1,n
#define OK Ll<=l&&r<=Rr
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
#define pb push_back
#define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i])
#define E(x) for(auto y:p[x])
#define Pi pair<int,int>
#define ui unsigned int
#define YY puts("Yes"),exit(0)
#define NN puts("No"),exit(0)
#define yy return puts("Yes"),void()
#define nn return puts("No"),void()
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
inline void pf(int x){if(x<0) putchar('-'),x=-x;if(x>9)pf(x/10);putchar(x%10+48);}
using namespace std;
const int N=1e5+5,M=1e6+5,inf=(1LL<<30)-1,mod=1e9+7;
const ll llf=1e18;
inline void add(int &a,int b){((a+=b)>=mod) and (a-=mod);}
inline int Add(int a,int b){return add(a,b),a;}
inline int mul(int a,int b){return 1LL*a*b%mod;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline void red(int &a,int b){add(a,mod-b);}
inline int Red(int a,int b){return red(a,b),a;}
inline int qp(int a,ll b){if(!b)return 1;int c=qp(a,b>>1LL);Mul(c,c);if(b&1)Mul(c,a);return c;}
inline int INV(int x){return qp(x,mod-2);}
inline bool che(int x,int p){return (x>>p)&1LL;}
int n,m;
ui ans=0;
struct node{
	int a,b,c,d;
}a[N];
struct lim{
	int a,b,c;
}A[N],B[N],C[N],D[N];
ui t[N],s[N];
inline void ad(int x,ui k){
	while(x<=n)t[x]++,s[x]+=k,x+=x&-x;
}
inline ui get(int x){
	x=min(x,n);
	ui ans=0;
	while(x)ans+=t[x],x-=x&-x;
	return ans;
}
inline ui query(int x){
	x=min(x,n);
	ui ans=0;
	while(x)ans+=s[x],x-=x&-x;
	return ans;
}
vector<int>p[N];
inline void subtaskA(){
	repm(i){
		A[a[i].a].a=max(A[a[i].a].a,a[i].b+1),A[a[i].a].b=max(A[a[i].a].b,a[i].c+1);
		B[a[i].b].b=max(B[a[i].b].b,a[i].c+1);
		D[1].a=max(D[1].a,a[i].a+1),D[1].b=max(D[1].b,a[i].b+1),D[1].c=max(D[1].c,a[i].c+1);
	}
	ans+=(ui)(n-D[1].a+1)*(ui)(n-D[1].b+1)*(ui)(n-D[1].c+1);
	per(i,n-1,1)A[i].a=max(A[i].a,A[i+1].a),A[i].b=max(A[i].b,A[i+1].b),B[i].b=max(B[i].b,B[i+1].b);
	repn(i)p[A[i].a].pb(A[i].b);
	ui sum=0;
	per(i,n,1){
		ad(B[i].b,n-B[i].b+1);
		for(auto nw:p[i])if(nw<=n){
			sum+=(ui)(n-nw+1)*get(nw);
			sum+=query(n)-query(nw);
		}
	}
	cout <<ans+sum*(ui)(n-1);
}
ui ct[1005][1005],cs[1005][1005];
inline ui gett(int l,int r,int Ll,int Rr){
	r=min(r,n),Rr=min(Rr,n);
	if(l>r||Ll>Rr)return 0;
	return ct[r][Rr]+ct[l-1][Ll-1]-ct[l-1][Rr]-ct[r][Ll-1];
}
inline ui gets(int l,int r,int Ll,int Rr){
	r=min(r,n),Rr=min(Rr,n);
	if(l>r||Ll>Rr)return 0;
	return cs[r][Rr]+cs[l-1][Ll-1]-cs[l-1][Rr]-cs[r][Ll-1];
}
inline void Main(){
	n=read(),m=read();
	bool speA=1;
	repm(i)a[i].a=read(),a[i].b=read(),a[i].c=read(),a[i].d=read(),speA&=a[i].d==1;
	if(n<=50&&m<=50){
		repn(A)repn(B)repn(C)repn(D){
			bool fl=1;
			repm(i)fl&=(A>a[i].a)+(B>a[i].b)+(C>a[i].c)+(D>a[i].d)>2;
			ans+=fl;
		}
		cout <<ans;
		return;
	}
	repn(i)A[i]=B[i]=C[i]=D[i]={1,1,1};
	/*236*/
	if(speA)return subtaskA();
	if(n<=1000&&m<=1000){
		repm(i){
			rep(j,a[i].a,a[i].a)A[j].a=max(A[j].a,a[i].b+1),A[j].b=max(A[j].b,a[i].c+1),A[j].c=max(A[j].c,a[i].d+1);
			rep(j,a[i].b,a[i].b)B[j].b=max(B[j].b,a[i].c+1),B[j].c=max(B[j].c,a[i].d+1);
			rep(j,a[i].d,a[i].d)D[j].c=max(D[j].c,a[i].c+1);
		}
		per(i,n-1,1)A[i].a=max(A[i].a,A[i+1].a),A[i].b=max(A[i].b,A[i+1].b),A[i].c=max(A[i].c,A[i+1].c),B[i].b=max(B[i].b,B[i+1].b),B[i].c=max(B[i].c,B[i+1].c),D[i].c=max(D[i].c,D[i+1].c);
		repn(a4){
			int a3=D[a4].c;
			ct[a4][a3]++,cs[a4][a3]+=n-a3+1;
		}
		repn(i)repn(j)ct[i][j]+=ct[i-1][j]+ct[i][j-1]-ct[i-1][j-1],cs[i][j]+=cs[i-1][j]+cs[i][j-1]-cs[i-1][j-1];
		repn(a1)rep(a2,A[a1].a,n){
			int a4=max(A[a1].c,B[a2].c),a3=max(A[a1].b,B[a2].b);
			ans+=(ui)(n-a3+1)*gett(a4,n,1,a3);
			ans+=gets(a4,n,a3+1,n);
		}
		cout <<ans;
		return;
	}
}
signed main(){
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
	int T=1;
	while(T--)Main();
	return 0;
}
